package _18_剑指OfferII;

// 对于异或运算 如果是高位权值，始终是大于低位权值的
// 1000 > 111 ,所以我们只要尽量保证高位权值为1就行
public class _067_剑指OfferII最大的异或 {


    TreeNode dummy = new TreeNode(-1);

    public int findMaximumXOR(int[] nums) {
        buildTree(nums);
        int max = 0;
        // 找到最大异或值
        for (int num : nums) {
            TreeNode node = dummy;
            for (int i = 30; i >= 0; --i) {
                if (((num >> i) & 1) == 0) {
                    if (node.right != null)
                        node = node.right;
                    else
                        node = node.left;
                } else {
                    if (node.left != null)
                        node = node.left;
                    else
                        node = node.right;
                }
            }
            max = Math.max(max, num ^ node.right.val);
        }
        return max;
    }

    public void buildTree(int[] nums) {
        for (int num : nums) {
            TreeNode node = dummy;
            for (int i = 30; i >= 0; --i) {
                if (((num >> i) & 1) == 0) {
                    if (node.left == null)
                        node.left = new TreeNode(0);
                    node = node.left;
                } else {
                    if (node.right == null)
                        node.right = new TreeNode(1);
                    node = node.right;
                }
            }
            // 底部存取数据
            node.right = new TreeNode(num);
        }
    }


    static class TreeNode {


        TreeNode left;

        TreeNode right;

        int val;

        public TreeNode(int val) {
            this.val = val;
        }
    }

}
